In packet switching, the messages to be switched are divided into information blocks called packets. In a self-routing switch having N inputs and N outputs, the output address of an input packet is embedded in the header of the packet. Typically, the switch consists of an interconnection of switch nodes. Based on the header information, the switch nodes execute a self-routing algorithm in a distributed manner without any external intervention. In such a system, packets may contend for the same internal link or same output port, resulting in packet conflicts.
Various switch architectures have been proposed during the last decade, most notably, the input-queued Batcher-banyan switch and the output-queued Knockout switch. The Batcher-banyan switch aims at eliminating packet contention completely. Basically, only a subset of input packets which have non-conflicting output destinations is switched at any given time slot or switch cycle. Consequently, the packets that have been denied output access must be buffered or queued at the inputs. The throughput of the Batcher-banyan switch is limited by the so-called head-of-line blocking; the packet losing contention at the head of the input queue may block all the subsequent packets, even though they may be destined for some idle outputs. In addition, the complexity of the switch is of order N (log N).sup.2, which is above the lower bound of N log N switch complexity established by Shannon. The performance, however, is perfect in the sense that packets are never routed to the wrong destinations and are never dropped due to contention.
The knockout switch allows packets from several inputs to reach the same output simultaneously, In this way, it is less likely for a packet to lose contention. Indeed, to the extent that this likelihood is sufficiently small, one can simply drop packets in excess of the available paths. This introduces a non-zero packet-loss probability, which, however, can be made arbitrarily small by increasing the number of paths from each input to each output. The complexity of the knockout switch is of order N.sup.2. A dilated-banyan network, which has the same design philosophy as the knockout switch, is of complexity order N log N (log log N).
An alternative switch-design approach is to employ deflection routing in the system. As a reference, both the tandem-banyan network and the shuffle-exchange network are based on deflection routing. In these systems, a packet that has lost contention in a switch node inside the overall switch is simply deflected to a wrong route temporarily. Redundancy is introduced in the routing process and the switch design so that the deflected packet can be routed in the later switching stages in a way that compensates for the earlier mistake. The key issue in designing such a system is to minimize the redundancy introduced by packet deflection. The concept of error-correcting routing in switching requires the right switch topology to achieve the N log N bound. Any arbitrary switch design is not likely to achieve the goal. For instance, the tandem-banyan network and the shuffle-exchange network are both of order N(log N).sup.2.